package sort;



import java.util.Arrays;

/**
 * 改进后的双向选择排序
 * 虽然时间复杂度还是O(n^2),但是实际上算法的效率优化了将近40-50%
 * 卡了我一下的地方是 最后一趟排序，中间的时候，minIndex + 1 = maxIndex时候 多理解理解把
 *
 * 综上所述，普通的双排并没有对原来的选择排序算法改进优化。
 * 主要问题在于最后交换前的分情况处理使算法变得复杂效率下降，如果我们能省略这一步的话，那才能真正意义上得到优化。
 *
 * 注意特殊情况才是是代码变复杂的地方。
 */
public class BiSelectSorting {
    public static void main(String[] args) {
        int[] arrays = {3, 9, 20, 1, 66, 33, 123, 900};
        select(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    /**
     * 从低到高进行排序，最外层低排序只需要length-1次。
     *
     * @param array
     */
    public static void select(int[] array) {
        int counts = 0;
        int length = array.length;
        System.out.println(length / 2);  // 如果是奇数，中间那个数也会自然有序
        for (int i = 0; i < length / 2; i++) {
            counts++;
            int min = array[i];
            int minIndex = i;
            int max = array[length - 1 - i];
            int maxIndex = length - 1 - i;
            for (int j = i+1 ; j <= length-2- i; j++) {
                if (min > array[j]) {
                    min = array[j];
                    minIndex = j;
                }
                if (max < array[length - 2 - i]) {
                    max = array[length - 2 - i];
                    maxIndex = length - 2 - i;
                }
            }
            // 交换最小值,如果有交换index有变化 -->
            if (minIndex != i) {
                array[minIndex] = array[i];
                array[i] = min;
            }
            // 交换最小值,如果有交换index有变化 -->
            if (maxIndex != length - 1 - i) {
                array[maxIndex] = array[length - 1 - i];
                array[length - 1 - i] = max;
            }
            System.out.println(counts + "次数 :" + Arrays.toString(array));

        }
    }

    /**
     * 双向选择排序算法 在选择算法的基础上，在一次循环中选择两个元素（最大和最小）。 以此减少循环次数提高效率
     */
    public void doubleSelectionSort(int[] arr) {
        int n = arr.length;// 数组长度
        for (int i = 0; i < n / 2; i++) {
            int rangeL = i; // 待排序数组的左边界
            int rangeR = n - i - 1; // 待排序数组的右边界
            int min = rangeL;
            int max = rangeR;

            for (int j = rangeL; j <= rangeR; j++) {
                // 如果有比最小值小的，就更新最小值下标
                if (arr[j] < arr[min]) {
                    min = j;
                }

                // 如果有比最大值大的，就更新最大值下标
                if (arr[j] > arr[max]) {
                    max = j;
                }
            }
            // 注意特殊情况
            if (rangeL == min && rangeR == max) {
                // 位置正确，不改动
            } else if (rangeL == min) {
                // 最小值在开始位置，则交换最大值到结束位置
                // 最大值在结束位置，则交换最小值到开始位置
                // 最大值在开始位置，最小值在结束位置
                // 最大值在开始位置，先交换最大值」

            }
        }
    }
}